package top.carrotguo.recursive;

/**
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 9:39 2018-05-14
 */
public class LCS {

    public static String LCS (String A, int n, String B, int m) {
        if (n == -1 || m== -1) {
            return "";
        } else if (A.charAt(n) == B.charAt(m)) {
            return LCS(A,n-1,B,m-1)+A.charAt(n);
        } else{
            return LCS(A,n-1,B,m).compareTo(LCS(A,n,B,m-1))>0?LCS(A,n-1,B,m) : LCS(A,n,B,m-1);
        }

    }

    public static void main(String[] args){
        System.out.print("最长公共子序列："+LCS("manimanihong",11,"manihng",6));
    }

}
